1. Field of the Invention
The present invention generally relates to design of electronic circuits, and more particularly, to optimal placement and layout of circuit components in computer-aided design (CAD) of electronic circuits.
2. Description of the Related Art
The physical design of an integrated circuit (IC) includes placement of circuit components on the IC prior to fabrication. FIG. 1 is a simplified drawing of an exemplary IC floorplan signified by the reference numeral 10. The floorplan 10 corresponds to the die of the IC when fabricated. Disposed near the periphery of the floorplan 10 is a plurality of bonding pads 12. Adjacent to the bonding pads 12 is normally disposed a plurality of I/O (Input/Output) cells 14. Surrounded by the I/O cells 14 and the pads 12 are internal cells, generally signified by the reference numeral 16. If the IC is a digital circuit, the internals cells 16 may comprise basic logic gates such as NAND or NOR gates. Alternatively, the cells 16 may be formed at a higher level than the basic logic gate level such as multiplexers or registers. If the IC is an analog circuit, the cells 15 can be basic transistors or opamps (operational amplifier). Very often, hardmacros, signified by the reference numeral 18, are also placed on the floorplan 10. These hardmacros 18 are relatively large blocks of circuits serving specific functions and may include PLL (Phase Lock Loop) or USB (Universal Serial Bus) for various digital and analog applications. Occasionally, a portion of the floorplan 10 is dedicated for the layout of a custom-made circuit 20 as shown in FIG. 1. For instance, the custom-made circuit 20 may be a pre-designed microprocessor core.
The process of placing all the aforementioned components 12, 14, 16, 18 and 20 on the floorplan 10 is called placement. However, the components 12, 14, 16, 18 and 20 need to electrically communicate with each other. Signal traces such as traces 22 are distributed on the floorplan to serve such purpose. The internal cells 16 also need to communicate with one another but the linking traces are not shown in FIG. 1 for conciseness and clarity. The process of linking the components together by the traces 22 is called routing.
When the IC industry was at its infancy, ICs could be placed and routed manually. As ICs become more complex, designing ICs manually no longer can be practical. Instead, IC placement and routing are computerized and automated under a specialized field called EDA (Electronic Design Automation). CAD tools are employed to accomplish the design tasks. In designing an IC using CAD tools, one of the main objectives is to place as many cells as possible on the IC layout so that the die space can be as fully utilized as possible with minimal empty-spaces among cells.
Excessive empty-spaces among cells on the IC layout pose several disadvantages. First, the empty-spaces needlessly elongate the signal traces such as traces 22 shown in FIG. 1. Longer traces 22 entail longer signal delays and therefore degrading the overall timing performance of the IC. However, the most undesirable consequence of all is the unnecessary enlargement of the die size of the IC. An IC with a larger die size is not only more expensive to manufacture in terms of material costs but also more susceptible to random defects during fabrication, thereby resulting in lower production yield.
Thus, in the placement and routing of ICs, there are always two conflicting requirements that need to be addressed. That is, on the one hand, there is a need to reduce the die size for the benefits as aforementioned. On the other hand, too aggressive in the pursuit of die-size reduction may render the IC after placement ultimately unroutable.
A common placement scheme for reducing die size is the use of a partition-based algorithm. Specifically, the floorplan of an IC is first partitioned by partition lines into respective parts. Then, cells are placed in the partitioned parts of the floorplan. During placement, the fundamental consideration is to arrive at a smallest possible number, which is the total wire lengths of all the cells when the cells are eventually routed. To prevent the problem of ultimate unroutability, Rent's rule is used as a guide. That is, routing traffic of each cell is first roughly estimated. The estimated cells are then placed on the partitioned floorplan. However, the estimation is gross at best and very often is far off from the reality. As such, some placed cells in the resultant layout may not be routable. Such an approach is exemplified by the disclosure in a technical paper authored by Yang et al., entitled “Congestion Estimation During Top-Down Placement,” IEEE Transaction on Computer-Aided Design of Integrated Circuit and Systems, Vo. 21, No. 1, pp. 72–80.
To rectify the aforementioned shortfall, that is, to ensure ultimate routability of the placed cells, an approach called the “balanced heuristic” has been suggested, as taught in a paper by Alpert et al., entitled, “Free Space Management for Cut-Based Placement,” Proceeding of ICCAD 2002, pp 746–751. In such an approach, the partitioned-based algorithm is still practiced. However, constraints are placed on each partitioned portion of the floorplan to avoid extremely crowded cell placement. Nevertheless, using such an approach, very often, empty-spaces are created by the balanced decision made in the early stages of the partition and may not be utilized and further possibly left idle as unused empty die spaces in the end. The unused die spaces of the IC could have been utilized productively as an alternative, for example, for resolving routing and placement congestions.
Other schemes to ensure ultimate routability of the placed cells employ techniques such as cell padding or cell inflation. Such schemes are typified by a paper by Brenner et al., entitled, “An Effective Congestion Driven Placement Framework,” Prod. ISPD 2002, pp. 6–10. These types of schemes artificially enlarge the cells prior to placement. As such, in a manner similar to Alpert et al. above, unused empty-spaces are created with the drawbacks as mentioned above.
There are schemes that address the unused empty-space in IC designs. One such scheme is disclosed in a technical paper authored by Yang et al., entitled, “Routability Driven White Space Allocation for Fixed-Die Standard Cell Placement,” Proc. of International Symposium Physical Design, 2002. In Yang et al., the emphasis is on alleviating congestions of designs having fixed-die sizes. At the final stage of the partition process, empty-spaces are dynamically allocated to ease “bins” that are considered congested. A bin is a pre-defined site on the floorplan available for cell placement. The allocation of empty-spaces to each bin is extrapolated and based on the corresponding congestion information of the row or column where the bin sits. Afterward, the process of low-temperate simulated annealing is employed to patch up for the loss of placement quality during the allocation process. This approach purely depends on a temperature-cooling schedule and the acceptance ratio is not usually predictable. Furthermore, simulated annealing is a computing-power intensive process and entails a long run time. Propagating cells or empty-spaces for long distances compound the situation further.
Complexities of ICs in terms of design are ever increasing. Advances in IC fabrication technologies allow more circuit functions to be integrated per unit area of IC space. At the same time, the trend of electronic products is toward mobilization. For example, mobile telephones and PDAs (Personal Digital Assistants), require ICs to be built with high degrees of miniaturization. There is a need to provide EDA tools capable of placing and routing ICs with optimal uses of IC die spaces.